package 链表.反转链表;

import java.util.Stack;

/**
 * @Program:IntelliJ IDEA
 * @description:
 * @author:香蕉你个啵娜娜 l.h-p@qq.com
 * @create:2023-01-05 20:27
 **/

public class Solution {
    public ListNode reverseList(ListNode head){
        Stack<ListNode> stack = new Stack<>();
        // 把链表节点全部摘掉放到栈中
        while (head != null){
            stack.push(head);
            head = head.next;
        }
        if (stack.isEmpty()){
            return null;
        }
        ListNode node = stack.pop();
        ListNode dummy = node;
        // 栈中的节点全部出栈，然后重新连成一个新的链表
        while (!stack.isEmpty()) {
            ListNode tempNode = stack.pop();
            node.next = tempNode;
            node = node.next;
        }
        // 最后一个节点就算反转前的头节点，一定要让他的next等于空，否则会构成环
        node.next = null;
        return dummy;
    }
}
